package com.leet.code.lcof;

public class Code40 {
    public static void main(String[] args) {

    }

    public int[] getLeastNumbers(int[] arr, int k) {

        if (k == 0 || arr.length == 0) {
            return new int[0];
        }

        if (k >= arr.length) {
            return arr;
        }
        sort(arr, 0, arr.length - 1, k);

        int[] arrK = new int[k];
        for (int i = 0; i < k; i++) {
            arrK[i] = arr[i];
        }
        return arrK;
    }


    public static void sort(int[] ints, int low, int high, int k) {
        if (low >= high) {
            return;
        }
        int l = low, h = high, t = ints[low];
        while (l < h) {
            while (ints[h] >= t && l < h) {
                h--;
            }

            while (ints[l] <= t && l < h) {
                l++;
            }

            int tmp = ints[l];
            ints[l] = ints[h];
            ints[h] = tmp;
        }

        int tmp = ints[low];
        ints[low] = ints[l];
        ints[l] = tmp;

        if (l == k) {
            return;
        } else if (l < k) {
            sort(ints, l + 1, high, k);
        } else {
            sort(ints, low, l - 1, k);
        }
    }

}
